<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8" />
		<meta name="keywords" content="递归 斐波拉契数列">
		<meta name="description" content="cdcoder是一个程序员学习交流平台，深度IT技术博客，移动开发博客,Web前端博客,企业架构博客,编程语言博客,互联网博客,数据库博客,IT blog,核心关注IT知识传播，共享。为更好的IT产业贡献一份微薄的力量。">
		<link rel="shortcut icon" href="/img/code.ico" />
		<link rel="bookmark" href="/img/code.ico" />
		<title>java相关知识</title>
		<link href="../css/index.css" rel="stylesheet">
		<link href="../css/github.css" rel="stylesheet" />
		<style>
			body {
				font-size: 16px;
				font: 400 16px/1.62 Georgia, "Xin Gothic", "Hiragino Sans GB", "Droid Sans Fallback", "Microsoft YaHei", sans-serif;
				font-family: 'PT serif', 微軟正黑體, 微软雅黑, 华文细黑, Microsoft Yahei, Hiragino Sans GB, sans-serif;
				color: #D0CCCC;

				text-shadow: 0px 0px 1px rgba(24, 22, 22, 0.35);
				background-color: #000;
			}
		</style>
	</head>
	<body>

		<header>
			<div class="logo"><a href="/index.html">徐思润博客</a></div>
			<nav>
				<ul id="starlist">
					<li><a href="/java/index.html">java</a></li>
					<li><a href="/data/index.html">算法与数据结构</a></li>
					<li><a href="/db/mysql.html">数据库</a></li>
					<li><a href="/distribution/index.html">分布式</a></li>
					<li><a href="/framework/index.html">架构</a></li>
					<li><a href="/interview/index.html">面试与被面试</a></li>
					<li><a href="/live/index.html">日常生活</a></li>
					<li><a href="/about.html">关于我</a></li>
					<li><a href="/baby/index.html">baby墙</a></li>
				</ul>
			</nav>
		</header>
		<div class="box">
			<h1 style="text-align: center;">递归</h1>
			<h2>1. 介绍</h2>
			<p>一说起递归，我想每个人都不陌生。举个从小就听过的例子：从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山，山里有座庙，庙里有个和尚，和尚在讲故事，从前有座山…</p>
			<p>还有你从两面相对的镜子中看到的画面，其实都是抽象出来的递归现象，但是严格来说并不是递归，因为会一直重复下去，没有终止条件，那就称为死循环了。有关递归和死循环的异同我们之后会说到，那么现在先来了解一下什么是递归?</p>
			<p>那么什么是递归呢? <strong>要理解递归，就得先了解什么是递归</strong>，实际上这句话就是一个递归。这么说可能不好理解，接下来我举个简单的例子来解释这段话的意义。</p>
			<p>假设我们现在都不知道什么是递归，我们自然想到打开浏览器：输入到谷歌的网页，点击搜索递归，然后在为维基百科中了解到了递归的基本定义。在了解到了递归实际上是和栈有关的时候，你又蒙圈了，什么是栈呢？数据结构没学清楚，此时的你只能又打开谷歌，搜索什么是栈。接下来你依次了解了内存/操作系统。在你基本了解好知识之后，你通过操作系统了解了内存，通过内存了解了栈，通过栈了解了什么是递归这下你恍然大悟！原来这就是递归啊！</p>
			<p>这下应该有点明白了吧，这个过程其实就是递归的过程，如果不了解递归，那就先了解什么是递归，可能你会说这是个循环并不是递归，我们前面说到，递归是需要终止条件的，那么<strong>你明白递归是什么</strong>其实就是终止条件。整个过程，搜索引擎充当递归函数(只是形象的假设)。在你去依次查找递归/栈/内存/操作系统的过程为前行阶段，在你都了解完之后，反回去了解含义的过程为退回阶段。如果还是不太清楚，可以接着看下面的例子。</p>
			<h1 data-breakpage>2. 示例</h1>
			<p>也许之前你在网络上看到过这张图片:</p>
			<p><img src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/3de371af6d83b9e3e15d8b76f4bdf058a3120ef9dcb0a7e8fbbb30092dc28f87da6a27b3db55a5e69014db2153ef1bc3?pictype=scale&from=30013&version=3.3.3.3&uin=182478932&fname=5b6fac208b0ad.jpg&size=750'
				/></img></p>
			<p>实际上这张图就很形象地表达出了递归，这句<strong>吓得我抱起了抱着抱着抱着我的小鲤鱼的我的我的我</strong>如果从字面意义上看可能看不出是什么意思，那么我们可以通过代码来实现同样的效果:</p>
			<pre class='language-java' lang='java'><code>
    public static void recursion( int depth){
        System.out.println("抱着");
        if(depth<0){
            System.out.println("我的小鲤鱼");
        }else {
            recursion(--depth);  // 递归调用
        }
        System.out.println("我的");
    }

    public static void main(String[] args) {
        System.out.println("吓得我抱起了");
        recursion(1);
    }
</code></pre>
			<p>在终端的打印结果为如下，可以看到和上面的那段话是一样的:</p>
			<p><img src='https://picabstract-preview-ftn.weiyun.com/ftn_pic_abs_v3/7cb92fb9413a221579ca64113f783c9c681513cabf54c5fc59ca6e612efc074096077a417f014c187b5797656548fa9e?pictype=scale&from=30013&version=3.3.3.3&uin=182478932&fname=20170508113017.png&size=750'
					  /></img></p>
			<p>代码其实十分简单，但是需要理解的是:<code>if</code>代码块的条件(<code>!depth</code>)为递归调用的终止条件，在<code>else</code>代码块内递归调用函数.我们前面有说到递归的过程是存在前行和退回阶段的，那么在前行阶段我们在每次调用函数后，打印出了”抱着”，并且当<code>depth≠0</code>时重新调用该函数;在退回阶段，将会去执行代码<code>console.log(&#39;的我&#39;)<span
					 style='font-family:"Open Sans", "Clear Sans", "Helvetica Neue", Helvetica, Arial, sans-serif'>;</span></code>再打印出”的我”.</p>
			<p><a href='https://www.zhihu.com/people/chuyue/activities'>褚跃跃</a>的图也能比较清楚地反映出这个过程:</p>
			<p><a href='https://i.loli.net/2018/08/12/5b6fac206abe6.jpg'><img src='https://i.loli.net/2018/08/12/5b6fac206abe6.jpg'
					 alt='enterReturn.jpg' referrerPolicy='no-referrer' /></a></p>
			<p>好了!这下你应该明白什么是递归了吧?如果你还没有明白什么是递归的话，你可以看<a href='https://pushy.site/2018/02/20/recursion/'>什么是递归？</a></p>
			<h1 data-breakpage>3. 应用</h1>
			<h2>3.1 斐波拉契数列</h2>
			<p>有关递归应用的应用有很多，例如注明的<a href='https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fr=aladdin&fromid=10078434&fromtitle=%E6%96%90%E6%B3%A2%E6%8B%89%E5%A5%91%E6%95%B0%E5%88%97'>斐波拉契数列</a>就可以通过递归来实现:</p>
			<pre><code>def fib(x):
    if x &lt; 2:
        return 0 if x == 0 else 1
    # 当x &gt; 2时，开始递归调用fib()函数:
    return fib(x - 1) + fib(x - 2)

print(fib(6))  # 打印结果为:8
</code></pre>
			<p>这里需要对<code>i&lt;2</code>时的特殊情况做出判断，当<code>x==0</code>时，直接返回<code>0</code>，当<code>x==1</code>时，直接返回<code>1</code></p>
			<h2>3.2 遍历文件</h2>
			<p>首先我们需要了解遍历的算法:定义的<code>file_display</code>函数以某个目录(<code>/home/pushy</code>)作为遍历的起点.遇到一个子目录时，就先接着遍历子目录(递归调用函数)。遇到一个文件时，就直接对改文件进行操作(这里只打印出文件的文件名):</p>
			<pre><code>import os

def file_display(filepath):
	for each in os.listdir(filepath):
    	# 得到文件的绝对路径:
		absolute_path = os.path.join(filepath， each)
        # 得到是否为文件还是目录的布尔值:
		is_file = os.path.isfile(absolute_path)
		if is_file:
        	# 当前的绝对路径为文件:
			print(each)
		else:
        	# 当前的绝对路径为目录:
			file_display(absolute_path)

file_display(&#39;/home/pushy&#39;)
</code></pre>
			<p>这样我们就可以遍历到<code>/home/pushy</code>路径下的所有文件:</p>
			<p><a href='https://i.loli.net/2018/08/12/5b6fac208b78a.png'><img src='https://i.loli.net/2018/08/12/5b6fac208b78a.png'
					 alt='readFile.png' referrerPolicy='no-referrer' /></a></p>
			<p>另外我们还可以使用递归来创建目录:</p>
			<pre><code>import os

def createFile(dirname):
    exits = os.path.exists(dirname)
    if exits:
        return True
    else:
        # 开始递归调用函数，并接受其返回值:
        rec_result = createFile(os.path.dirname(dirname))
        if rec_result:
            # 如果不存在该目录，则创建dirname的目录，并返回已经创建(存在)的值True:
            os.mkdir(dirname)
            return True

createFile(&#39;./aa/bb/cc&#39;)
</code></pre>
			<h1 data-breakpage>4. 循环与递归</h1>
			<p>好了，递归的知识差不多介绍完了。如果看完上边大概已经了解了循环和递归的区别了。对了!简单来说，循环是有去无回，而递归则是有去有回(因为存在终止条件)。</p>
			<p>举个栗子，你用你手中的钥匙打开一扇门，结果去发现前方还有一扇门，紧接着你又用钥匙打开了这扇门，然后你又看到一扇们…但是当你开到某扇门时，发现前方是一堵墙无路可走了，你选择原路返回——这就是递归</p>
			<p>但是如果你打开一扇门后，同样发现前方也有一扇们，紧接着你又打开下一扇门…但是却一直没有碰到尽头——这就是循环。</p>

		</div>
		<footer>
			<p>Design by <a href="http://cdcoder.cn" target="_blank">徐思润个人博客</a> </p>
			<p>备案号：<a href="/">蜀ICP备15014105号-1</a></p>
			<script type="text/javascript" src="https://s96.cnzz.com/z_stat.php?id=1277229191&web_id=1277229191"></script>
		</footer>
		<script src="../js/rainbow.min.js"></script>
		<script src="../js/java_h.js"></script>
	</body>
</html>
